// https://leetcode.cn/problems/median-of-two-sorted-arrays/?envType=study-plan-v2&envId=binary-search

// 算法思路总结：
// 1. 递归二分查找两个有序数组的第k小元素
// 2. 每次比较排除k/2个不可能元素
// 3. 处理数组长度差异和边界条件
// 4. 根据总长度奇偶性计算中位数
// 5. 时间复杂度：O(log(m+n))，空间复杂度：O(log(m+n))

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) 
    {
        int tot = nums1.size() + nums2.size();

        if (tot % 2 == 0)
        {
            int left = find(nums1, 0, nums2, 0, tot / 2);
            int right = find(nums1, 0, nums2, 0, tot / 2 + 1);
            return (left + right) / 2.0;
        }

        return (double)find(nums1, 0, nums2, 0, tot / 2 + 1);
    }

    int find(vector<int>& nums1, int i, vector<int>& nums2, int j, int k)
    {
        if (nums1.size() - i > nums2.size() - j) return find(nums2, j, nums1, i, k);
        if (nums1.size() == i)  return nums2[j + k - 1];
        if (k == 1) return min(nums1[i], nums2[j]);

        int si = min((int)nums1.size(), i + k / 2);
        int sj = j + k - k / 2;

        if (nums1[si - 1] > nums2[sj - 1])
            return find(nums1, i, nums2, sj, k - (sj - j));
        else 
            return find(nums1, si, nums2, j, k - (si- i));
    }
};

int main()
{
    vector<int> nums11 = {1,3}, nums12 = {2};
    vector<int> nums21 = {1,2}, nums22 = {3,4};

    Solution sol;

    cout << sol.findMedianSortedArrays(nums11, nums12) << endl;
    cout << sol.findMedianSortedArrays(nums21, nums22) << endl;

    return 0;
}